﻿#include "MaxestSumOfRingSubArr.h"


#ifdef DEV_TEST
#include <gtest/gtest.h>
class MaxestSumOfRingSubArrTestCase
{
public:
	std::string arrNums;

	friend std::ostream& operator<<(std::ostream& os, const MaxestSumOfRingSubArrTestCase& obj)
	{
		return os << "arrNums: " << obj.arrNums;
	}
};
class MaxestSumOfRingSubArrTest :public SolutionTestor<IMaxestSumOfRingSubArr, testing::TestWithParam<MaxestSumOfRingSubArrTestCase>>
{
protected:
	void LoadSolutions(std::vector<IMaxestSumOfRingSubArr*>& solutions) override
	{
		solutions = {
			new MaxestSumOfRingSubArr::DP,
			new MaxestSumOfRingSubArr::MaxAndMin,
		};
	}
};

TEST_P(MaxestSumOfRingSubArrTest, getMaxSumOfRingSubArr)
{
	TestForSolutions([](IMaxestSumOfRingSubArr* solution)
		{
			const auto testCase = GetParam();
			std::vector<int> arr;
			FormatedUtil::parseFormated(arr, testCase.arrNums);

			//期望的环形子数组最大和
			int expectResult = INT_MIN;
			if (arr.empty())
				expectResult = 0;
			const int arrSize = arr.size();
			//arr中每个元素作为环形子数组开始时，能够得到的最大和
			for (int start = 0; start < arrSize; ++start)
			{
				int maxSum = arr[start];
				int sum = arr[start];
				for (int i = 1; i < arrSize; ++i)
				{
					sum += arr[(start + i) % arrSize];
					maxSum = std::max<>(sum, maxSum);
				}
				expectResult = std::max<>(maxSum, expectResult);
			}

			//与solution的结果对比
			const auto result = solution->getMaxSumOfRingSubArr(arr);
			EXPECT_EQ(result, expectResult);
		});
}

INSTANTIATE_TEST_SUITE_P(ValidityTestCases, MaxestSumOfRingSubArrTest, testing::Values(
	MaxestSumOfRingSubArrTestCase{ "[]" },
	MaxestSumOfRingSubArrTestCase{ "[5,-3,5]" },
	MaxestSumOfRingSubArrTestCase{ "[3,-2,2,-3]" },
	MaxestSumOfRingSubArrTestCase{ "[1,1,1,1,1,1]" },
	MaxestSumOfRingSubArrTestCase{ "[-1,-1,-1,-1,-1,-1]" },
	MaxestSumOfRingSubArrTestCase{ "[1,-2,0,0,0,1,1,-2,5,1,3,2,4,0,0,0]" },
	MaxestSumOfRingSubArrTestCase{ "[-116,193,80,187,467,-40,-452,148,403,-356,14,-245,204,413,481,-125,167,-32,-409,472,417,448,188,-45,-289,390,-181,-275,-110,-490,497,-417,315,-243,-367,-254,-112,152,232,387,151,-361,434,-455,-110,154,-59,-102,451,-318,484,258,-430,499,-498,374,-386,-400,-55,344,185,64,440,4,166,488,-379,-110,47,-359,-437,380,-78,235,-429,467,-428,-110,1,-330,137,-432,-336,-141,106,323,436,272,232,-112,-314,107,304,72,-371,113,232,434,90,-27,81,-22,-155,337,53,-383,-241,-367,-125,404,-497,254,296,-95,249,-431,-368,-177,396,457,-274,285,371,-314,-40,358,158,190,95,340,-230,233,-3,-277,-482,432,136,-337,-145,-493,-402,489,-41,-317,257,365,-423,269,397,-249,-448,-224,-113,-248,80,337,-495,-245,117,-211,-173,341,-397,-274,-252,284,318,114,322,-353,395,441,-50,319,-361,-275,371,-147,-34,494,-16,404,206,-489,460,407,-426,-29,234,174,265,429,293,-427,-481,166,158,382,-419,-201,251,-159,-404,-398,474,-224,-48,420,15,-104,186,366,458,389,264,212,-251,-396,59,85,12,71,121,133,149,29,125,383,-310,-256,476,175,357,371,424,-417,427,124,370,8,-180,22,220,-341,-13,-142,157,168,-455,319,496,64,182,215,111,126,306,164,244,-205,-15,-285,-463,130,-442,-169,65,-440,-63,170,430,0,-253,-152,-269,-265,145,276,453,-61,432,-242,-242,-359,425,-315,-46,208,-67,362,454,472,322,109,61,-409,-130,277,381,-403,-229,-270,-430,414,-292,-244,137,-160,151,417,-216,285,-213,-245,468,-325,364,337,202,75,-11,168,242,-161,-378,-104,-215,455,262,-149,222,341,-126,468,-9,464,-58,-11,301,-194,-373,-164,150,470,242,-394,-303,-91,496,339,-225,-2,227,357,312,-329,-324,-484,-333,354,261,235,115,98,-171,-407,30,-129,-54,-448,-465,123,-394,-70,311,493,453,-467,-265,-330,-43,476,-111,-85,-113,329,352,-366,-11,255,109,424,421,197,107,-478,-139,-144,317,395,239,-225,135,-139,-9,109,-301,395]" }
));
#endif